package 开始的剑指offer8月.查找算法;
// https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
public class 剑指Offer53II中缺失的数字0816 {
    // class Solution {
//     public int missingNumber(int[] nums) {
//         int i = 0, j = nums.length - 1;
//         while(i <= j) {
//             int m = (i + j) / 2;
//             if(nums[m] == m) i = m + 1;
//             else j = m - 1;
//         }
//         return i;
//     }
// }

    class Solution {
        public int missingNumber(int[] nums) {
            int l = 0, r = nums.length - 1;
            while (l <= r){
                int mid = l + (r-l)/2;
                if(mid < nums[mid])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            return l;
        }
    }

}
